#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=10000, maxm=10000, maxk=4, inf=0x7ffffff;

 long long min(long long a, long long b) {
  return a<b ? a : b;
}

class Graph {
public:
  int n, m, ind[maxn+1], to[2*maxm+1], link[2*maxm+1], val[2*maxm+1];
  long long dis[maxn+1];

  void addSide(int u, int v, int w) {
    m++;
    to[m] = v;
    val[m] = w;
    link[m] = ind[u];
    ind[u] = m;
  }

  void spfa() {
    static bool book[maxn+1];
    static int que[maxn+1];
    for (int i=1; i<=n; i++) {
      book[i] = true, que[i] = i;
    }
    for (int h=0, t=n; h!=t; ) {
      h = h%n+1;
      int o=que[h];
      book[o] = false;
      for (int i=ind[o]; i; i=link[i]) {
	if (dis[to[i]]>dis[o]+val[i]) {

	  if (!book[to[i]]) {
	    t = t%n+1;
	    que[t] = to[i];
	    book[to[i]] = true;
	  }
	}
      }
    }
  }
};

int main() {
#ifdef DEBUG
  freopen("3400.in", "r", stdin);
  freopen("3400.out", "w", stdout);
#endif

  static Graph g;
  static long long f[maxn+1][1<<(2*maxk)], good[1<<(2*maxk)], h[maxk+1][1<<(2*maxk)];
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  g.n = n;
  for (int i=1; i<=m; i++) {
    int a, b, w;
    scanf("%d %d %d", &a, &b, &w);
    g.addSide(a, b, w);
    g.addSide(b, a, w);
  }

  memset(f, 90, sizeof(f));
  memset(good, 90, sizeof(good));
  memset(h, 90, sizeof(h));
  for (int i=1; i<=k; i++) {
    f[i][1<<i] = f[n-i+1][1<<(2*k-i+1)] = 0;
  }
  for (int i=k+1; i<=n-k; i++) {
    f[i][0] = 0;
  }
  for (int i=0; i<(1<<k); i++) {
    for (int j=1; j<=n; j++) {
      for (int k=(i-1)&i; k>0; k=(k-1)&i) {
	for (int l=g.ind[j]; l; l=g.link[l]) {
	  f[j][i] = min(f[j][i], f[g.to[l]][k]+g.val[l]+f[j][i-k]);
	}
      }
      g.dis[j] = f[j][i];
    }
    g.spfa();

    for (int j=1; j<=n; j++) {
      f[j][i] = g.dis[j];
      good[i] = min(good[i], f[j][i]);
    }
  }

  for (int i=1; i<=k; i++) {
    for (int j=0; j<(1<<(2*k)); j++) {
      if (((j>>i)&1) && ((j>>(2*k-i+1))&1)) {
	for (int k=(j-1)&j; k<j && k>=0; k=(k-1)&j) {
	  h[i][j] = min(h[i][j], h[i-1][k]+h[i-1][j-k]);
	}
      }
    }
  }

  printf("%lld", h[k][(1<<(2*k))-1]);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
